package 实验二_顺序表的实现和应用;

/**
 * by 孙彪 2215805342 2025.3.5
 * 顺序表的实现和应用
 */

/**
 * 顺序表的实现及测试
 */
public class Test {
    public static void main(String[] args) {
        // 初始化顺序表，内容为：11, 15, 23, 32, 44, 65, 67, 88
        SeqList list = new SeqList(new int[]{11, 15, 23, 32, 44, 65, 67, 88});
        System.out.println("初始表为：" + list + "，表长为：" + list.getSize());
        System.out.println("*********************************************************************");

        // 插入操作（下标从0开始，合法区间为0～size）
        list.insert(2, 8);   // 在下标2处插入8
        System.out.println("插入元素8后，表状态为：" + list + "，表长为：" + list.getSize());
        list.insert(3, 12);  // 在下标3处插入12
        System.out.println("插入元素12后，表状态为：" + list + "，表长为：" + list.getSize());
        list.insert(4, 24);  // 在下标4处插入24
        System.out.println("插入元素24后，表状态为：" + list + "，表长为：" + list.getSize());
        list.insert(5, 32);  // 在下标5处插入32
        System.out.println("插入元素32后，表状态为：" + list + "，表长为：" + list.getSize());
        list.insert(6, 87);  // 在下标6处插入87
        System.out.println("插入元素87后，表状态为：" + list + "，表长为：" + list.getSize());
        list.insert(7, 91);  // 在下标7处插入91
        System.out.println("插入元素91后，表状态为：" + list + "，表长为：" + list.getSize());
        System.out.println("*********************************************************************");

        // 查找操作（位置以1开始计数）
        searchAndPrint(list, 24);
        searchAndPrint(list, 28);
        searchAndPrint(list, 32);
        searchAndPrint(list, 86);
        searchAndPrint(list, 91);
        System.out.println("*********************************************************************");

        // 删除操作：删除指定元素的首次出现
        list.delete(11);
        System.out.println("删除元素11后，表状态为：" + list + "，表长为：" + list.getSize());
        list.delete(23);
        System.out.println("删除元素23后，表状态为：" + list + "，表长为：" + list.getSize());
        list.delete(32);
        System.out.println("删除元素32后，表状态为：" + list + "，表长为：" + list.getSize());
        list.delete(67);
        System.out.println("删除元素67后，表状态为：" + list + "，表长为：" + list.getSize());
        list.delete(88);
        System.out.println("删除元素88后，表状态为：" + list + "，表长为：" + list.getSize());
        System.out.println("*********************************************************************");

        // 清空顺序表：每次删除第一个元素，并打印当前状态
        System.out.println("清空顺序表：");
        while (list.getSize() > 0) {
            list.deleteAt(0);
            if (list.getSize() > 0) {
                System.out.println(list + "，表长为：" + list.getSize());
            } else {
                System.out.println("表长为：0");
            }
        }
    }

    // 查找元素，并打印结果（位置以1开始计数）
    private static void searchAndPrint(SeqList list, int element) {
        int pos = list.search(element);
        if (pos != -1) {
            System.out.println("元素" + element + "在顺序表中的位置为" + (pos + 1));
        } else {
            System.out.println("元素" + element + "不在顺序表中");
        }
    }
}

/**
 * 顺序表类：内部使用数组存储数据，支持插入、删除、查找等操作
 */
class SeqList {
    private int[] data;    // 存储数据的数组
    private int size;      // 当前顺序表的元素个数
    private int capacity;  // 数组容量

    // 构造一个空顺序表，指定初始容量
    public SeqList(int capacity) {
        this.capacity = capacity;
        data = new int[capacity];
        size = 0;
    }

    // 通过数组初始化顺序表
    public SeqList(int[] elems) {
        capacity = Math.max(10, elems.length);
        data = new int[capacity];
        // 将数组中的元素依次复制到顺序表中
        for (int i = 0; i < elems.length; i++) {
            data[i] = elems[i];
        }
        size = elems.length;
    }

    // 获取顺序表的当前长度
    public int getSize() {
        return size;
    }

    // 在指定位置插入元素（下标从0开始，合法区间为0～size）
    public boolean insert(int index, int value) {
        if (index < 0 || index > size) {
            return false;
        }
        // 当容量不足时，进行扩容
        if (size == capacity) {
            capacity *= 2;
            int[] newData = new int[capacity];
            System.arraycopy(data, 0, newData, 0, size);
            data = newData;
        }
        // 将指定位置及之后的元素后移一位
        for (int i = size; i > index; i--) {
            data[i] = data[i - 1];
        }
        data[index] = value;
        size++;
        return true;
    }

    // 删除指定元素的首次出现（若存在），返回true表示删除成功
    public boolean delete(int value) {
        int index = search(value);
        if (index == -1) {
            return false;
        }
        return deleteAt(index);
    }

    // 删除指定下标处的元素
    public boolean deleteAt(int index) {
        if (index < 0 || index >= size) {
            return false;
        }
        // 将后续元素向前移动覆盖要删除的元素
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        size--;
        return true;
    }

    // 查找元素，返回其在数组中的下标；若不存在，则返回-1
    public int search(int value) {
        for (int i = 0; i < size; i++) {
            if (data[i] == value) {
                return i;
            }
        }
        return -1;
    }

    // 重写toString方法，输出时每个数字后添加一个空格
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        // 只输出有效数据部分
        for (int i = 0; i < size; i++) {
            sb.append(data[i]);
            if (i < size - 1) {
                sb.append(" ");
            }
        }
        return sb.toString();
    }
}
